package _08_动态规划;
/*
    动态规划求解斐波那契
 */
public class Fib {

    int fib(int n){
        //创建一个备忘录，来进行备忘录
        int[] memo = new int[n+1];
        return helper(memo,n);
    }

    int helper(int[] memo,int n){
        if(n==0 || n==1) return n;
        if(memo[n] != 0 ) return memo[0];
        memo[n] = helper(memo,n-1) + helper(memo,n-2);
        return memo[n];
    }

    int fibNR(int n){
        if(n == 0) return 0;
        int[] dp = new int[n+1];
        dp[1] = 1; //Base case
        for(int i=2;i<=n;++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}
